/*
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        /*
        vector<vector<int>> res;
        vector<int> item;
        dfs(0,1,n,k,res,item);
        return res;
        */
        vector<vector<int>> res;
        vector<int> range;
        vector<bool> visited(9,false);
        dfs(res,range,visited,n,0,k,1);
        return res;
    }

private:
    /*
    void dfs(int sum,int idx,int target,int max_len,vector<vector<int>>& res,vector<int>& item){
        if(sum==target&&item.size()==max_len){
            res.push_back(item);
        }
        for(int i=idx;i<10;i++){
            if(sum>target||item.size()>max_len){
                continue;   
            }
            sum=sum+i;
            item.push_back(i);
            dfs(sum,i+1,target,max_len,res,item);
            sum=sum-i;
            item.pop_back();
        }
    }
    */
    void dfs(vector<vector<int>>& res,vector<int>& range,vector<bool>& visited,int target,int len,int max_len,int idx){
        if(target==0&&len==max_len){
            res.push_back(range);
            return;
        }
        if(len>=max_len&&target!=0){
            return;
        }
        for(int i=idx;i<=9;i++){
            if(!visited[i-1]){
                range.push_back(i);
                visited[i-1]=true;
                dfs(res,range,visited,target-i,len+1,max_len,i+1);
                visited[i-1]=false;
                range.pop_back();
            }
        }
    }
};